package sort

import "fmt"

func heapsort(arr []int)[]int{
	length:= len(arr)
	for i:=0;i<length ;i++ {
		lastmesslen:= length-i
		heapsortMax(arr, lastmesslen)
		fmt.Println(arr)
		if i<length{
			arr[0],arr[lastmesslen-1] = arr[lastmesslen-1],arr[0]
		}
		fmt.Println("ex",arr)
	}
	return arr
}

//堆paix
func heapsortMax(arr []int, length int) []int {
	//length:= len(arr)

	if length<=1{
		return arr
	}else{
		depth:= length/2-1 //深度
		for i:=depth;i>=0;i--{  //循环所有的三节点
			topmax:=i //假定最大的在i的位置
			leftchild:=2*i+1
			rightchild:=2*i+2
			if leftchild<= length-1 && arr[leftchild]>arr[topmax]{
				topmax = leftchild //如果左边大则记录
			}
			if rightchild<=length-1 && arr[rightchild]>arr[topmax]{
				topmax = rightchild //如果右边大则记录
			}

			if topmax!=i{ //确保i的值最大
				arr[i],arr[topmax] = arr[topmax],arr[i]
			}

		}
	}
	return arr

}
